#define _CRT_SECURE_NO_WARNINGS 1

#include"sort.h"

Stack* StackInit()
{
	Stack* ST = (Stack*)malloc(sizeof(Stack));
	if (ST == NULL)
	{
		perror("malloc error");
		exit(-1);
	}

	ST->arr = NULL;
	ST->top = 0;
	ST->capacity = 0;
	return ST;
}

void StackPush(Stack* ST, int x)
{
	assert(ST);

	if (ST->top == ST->capacity)
	{
		int newcapacity = ST->capacity == 0 ? 4 : (ST->capacity) * 2;
		int* new = (int*)realloc(ST->arr, newcapacity * sizeof(int));
		if (new == NULL)
		{
			perror("malloc error");
			exit(-1);
		}

		ST->arr = new;
		ST->capacity = newcapacity;
	}

	ST->arr[ST->top] = x;
	ST->top++;
}

void StackPop(Stack* ST)
{
	assert(ST);
	assert(!StackEmpty(ST));

	ST->top--;
}

int StackRead(Stack* ST) 
{
	assert(ST);
	assert(!StackEmpty(ST));

	return ST->arr[ST->top - 1];
}

void StackDestroy(Stack* ST)
{
	assert(ST);

	free(ST->arr);
	free(ST);
}

bool StackEmpty(Stack* ST) 
{
	assert(ST);

	return ST->top == 0;
}


Queue* QueueInit()
{
	Queue* Q = (Queue*)malloc(sizeof(Queue));
	if (Q == NULL)
	{
		perror("malloc error");
		exit(-1);
	}

	Q->head = NULL;
	Q->tail = NULL;
	return Q;
}

QNode* BuyQNode(int x)
{
	QNode* new = (QNode*)malloc(sizeof(QNode));
	if (new == NULL)
	{
		perror("malloc error");
		exit(-1);
	}

	new->val = x;
	new->next = NULL;

	return new;
}

void QueuePush(Queue* Q, int x)
{
	assert(Q);

	if (QueueEmpty(Q))
	{
		Q->head = Q->tail = BuyQNode(x);
	}
	else
	{
		Q->tail->next = BuyQNode(x);
		Q->tail = Q->tail->next;
	}
}

void QueuePop(Queue* Q)
{
	assert(Q);
	assert(!QueueEmpty(Q));

	if (Q->head == Q->tail)
	{
		free(Q->head);
		Q->head = Q->tail = NULL;
	}
	else
	{
		QNode* Next = Q->head->next;
		free(Q->head);
		Q->head = Next;
	}
}

int QueueRead(Queue* Q)
{
	assert(Q);
	assert(!QueueEmpty(Q));

	return Q->head->val;
}

void QueueDestroy(Queue* Q)
{
	assert(Q);

	while (!QueueEmpty(Q))
	{
		QueuePop(Q);
	}
	free(Q);
}

bool QueueEmpty(Queue* Q) 
{
	assert(Q);

	return Q->head == NULL;
}